The present invention relates to efficient hardware implementations of a binary search algorithm.
The term “binary search” refers to an algorithm for locating the position of an element in a sorted list. Initially, the algorithm compares the middle element of the sorted list to a key value. If that element is equal to the key, then the position has been found. Otherwise, the upper half or lower half of the list is chosen for further searching based on whether the key is greater than or less than the middle element. This continues iteratively until either the position is found, or the key is determined not to be in the list. Each iteration of the binary search algorithm reduces the number of elements needed to be checked by a factor of two, finding the key (if it exists in the list), or determining that the key is not present, in logarithmic time. This is to be contrasted with linear search in which the key is compared to each element in an unsorted list sequentially until the position is found.